from typing import List


class Solution:
    """
    方法：从矩阵右上角开始搜索，利用矩阵排序特性进行剪枝
    Args:
        matrix: List[List[int]], 二维整数矩阵，每行每列都按升序排列
        target: int, 要搜索的目标值
    Returns:
        bool, 如果找到目标值返回True，否则返回False
    Time: O(m + n), 最坏情况下需要遍历矩阵的一行和一列
    Space: O(1), 只使用了常数级别的额外空间
    """
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        i, j = 0, n - 1 # 从右上角开始
        while i < m and j >=0:
            if matrix[i][j] == target:
                return True
            if matrix[i][j] < target:
                i += 1 # 这一行剩余元素全部小于 target，排除
            else:
                j -= 1 # 这一列剩余元素全部大于 target，排除
        return False